/* 费用流 算法应用
* 1.基础概念
    费用流即最小/大费用最大流（即最大可行流中的最小/大费用）
    费用流：最大流时每条边上的可行流×该边上的费用

* 2.求解算法
    将 EK 算法中的 bfs 改为 spfa，spfa 用来求解源点 S 到 T 的最短/长路（即 S 到 T 上的最小路径费用和）
    在求最短/长路的同时找到一条增广路径，然后增加这部分的费用，直到找不到增广路径为止

    spfa不可处理负权回路，如果图中有负权回路，需要消圈

    只要当前沿着最短路径增广，则一定能求得最小费用流

* 本题:
    二分图最优匹配
    建立源点 s 和汇点 t，s 向所有工人表示的点连边，容量为 1，费用为 0，
                       所有的工作表示的点向 t 连边，容量为 1，费用为 0，
                       所有的工人表示的点向所有工作表示的点连边，容量足够大，费用为工人对待工作的效益，
    最后 s 到 t 的费用流即为所求

    如果工人 到某个工作 有流量，则说明该工人选择该工作
*/

#define DEBUG
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 110, M = 30010, INF = 0x3f3f3f3f;
int n, m, S, T;
int h[N], e[M], c[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];
int capa[N]; //仓库容量

void AddEdge(int a, int b, int cc, int ww)
{
    e[idx] = b, c[idx]=cc, w[idx]=ww, ne[idx]=h[a], h[a]=idx++;
    e[idx] = a, c[idx]=0, w[idx]=-ww, ne[idx]=h[b], h[b]=idx++;
}

bool spfa() 
{
    memset(d, 0x3f, sizeof d);
    memset(incf, 0, sizeof incf);

    int hh=0, tt=0;
    q[tt++]=S, d[S]=0, incf[S]=INF;

    while(hh!=tt)
    {
        int u=q[hh++];
        if(hh==N) hh=0;
        st[u]=false;

        for(int i=h[u]; ~i; i=ne[i])
        {
            int v=e[i];
            if(c[i] && d[v] > d[u]+w[i])
            {
                d[v] = d[u]+w[i];
                incf[v] = min(incf[u], c[i]);
                pre[v] = i;
                if(!st[v])
                {
                    st[v] = true; //如果之前没有访问过，则置已访问，除非有多条边可指向v，即在队列中有多次入队
                    q[tt++] = v;
                    if(tt==N) tt=0;
                }
            }
        }
    }
    return incf[T]>0;
}

int EK() 
{
    int cost=0;
    while(spfa())
    {
        cost+=incf[T]*d[T]; //当前流的最值流
        for(int i=T; i!=S; i=e[pre[i]^1])
        {
            c[pre[i]] -= incf[T]; c[pre[i]^1] += incf[T]; 
        }

    }
    return cost;
}

signed main()
{
    #ifdef DEBUG
        freopen("./in.txt","r",stdin);
    #else
        ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    #endif
    memset(h, -1, sizeof h);

    cin >> n;
    S=0, T=2*n+1;
    
    for(int i=1; i<=n; i++)
        AddEdge(S, i, 1, 0), AddEdge(i+n, T, 1, 0);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            int w; cin >> w;
            AddEdge(i, j+n, INF, w);
        }

    printf("%d\n", EK()); //最小费用流

    //最大费用流
    for(int i=0; i<idx; i+=2)
    {
        c[i]+=c[i^1], c[i^1]=0; //复原容量
        swap(w[i], w[i^1]); //费用取反，-新图最小流==原图最大流
    }
    printf("%d\n", -EK());

    return 0;
}